package demo1;

public class LeetCode76 {
    public String minWindow(String s, String t) {
        char[] arr1 = s.toCharArray();
        char[] arr2 = t.toCharArray();
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        int kinds = 0, begin = -1, min_lens = Integer.MAX_VALUE;
        for (char ch : arr2) if (hash2[ch]++ == 0) kinds++;
        for (int left = 0, right = 0, kind = 0; right < s.length(); right++) {
            char in = arr1[right];
            if (++hash1[in] == hash2[in]) kind++;
            while (kind == kinds) {
                if (right - left + 1 < min_lens) {
                    begin = left;
                    min_lens = right - left + 1;
                }
                char out = arr1[left++];
                if (hash1[out]-- == hash2[out]) kind--;
            }
        }
        if (begin == -1) return new String();
        else return s.substring(begin, begin + min_lens);
    }
}